﻿#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <memory>
#include <functional>
#include <iostream>

using namespace std;

// 以下是位运算专题，位运算类的题目有以下注意事项
// 基础位运算：
// m1. 给定一个数二进制表示的数 n, 确定 n 的第 x 位是 0 还是 1
//	   (n >> x) & 1, 结果是 0，表示第 x 位是0，否则是1
// 
// m2. 将一个数 n 的二进制表示的 第 x 位修改成 1
//	   n |= ( 1 << x )
// 
// m3. 将一个数 n 的二进制表示的 第 x 位修改成 0
//	   n &= (~(1 << x))
// 
// m4. 位图的思想
// 
// m5. 可以用n & (-n)提取一个数对应的二进制表示中最右侧的 1
//	   其中 n 是这个数对应的二进制表示
//	   原理说明，以 n = 10010010 为例
//	   -n 是通过 n 按位取反后加 1 得到的，即 -n = 01101101 + 1 = 011001110
//	   那么 -n 就相当于将 二进制表示中最右侧 的1 左边的所有比特位按位取反
//	   二进制表示中最右侧 的1 以及其右侧的所有比特位都不变
//	   此时在由于 1 & 0 = 0， 0 & 1 = 0, 所以 二进制表示中最右侧 的1 左边的所有比特位都变成0
//	   而且 0 & 0 = 0，二进制表示中最右侧 的1 右边的所有比特位都是0，那么 就能提取出一个数对应的最右侧的1
// 
// m6. 可以用n & (n - 1)删除一个数(n)二进制表示中最右侧的1
//	   其中 n 是这个数对应的二进制表示
//	   原理说明，以 n = 10010010 为例
//	   n - 1 是通过 不断借位，直到借到  二进制表示中最右侧 的 1 为止，即n - 1 = 10010001
//     那么 n - 1 就相当于将 二进制表示中最右侧 的1 右边的比特位 以及 二进制表示中最右侧 的1 按位取反
//	   二进制表示中最右侧 的1 左侧的所有比特位都不变
//	   此时在由于 1 & 1 = 1，0 & 0 = 0, 所以 二进制表示中最右侧 的1 左边的所有比特位不变
//	   而且 1 & 0 = 0， 0 & 1 = 0，二进制表示中最右侧 的1 右边的所有比特位都是0，
//	   那么就能把 n 的二进制表示中 对应的最右侧的1 以及后面的数都变为0，而其他二进制位不变
// 
//  m7. 异或运算的运算律
//      m1. a ^ 0 = a
//      m2. a ^ a = 0
//      m3. a ^ b ^ c = a ^ (b ^ c)
//
// 第37 题 ##########################################################################################
//371. 两整数之和
//给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。
//示例 1：       输入：a = 1, b = 2     输出：3
//
// a ^ b 能够实现 无进位相加
// (a & b) << 1 能够实现 获得两个数相加时所需要的 所有进位代表的数
// a + b = (a ^ b) + ((a & b) << 1) = a1 + b1
//       = (a1 ^ b1) + ((a1 & b1) << 1)
//       = ... = an ^ bn = an ^ 0 = an
//
class Solution1 {
public:
    int getSum(int a, int b) {
        while (b)
        {
            int tmp1 = a ^ b;
            b = (a & b) << 1;
            a = tmp1;
        }
        return a;
    }
};

// 第38 题 ##########################################################################################
//137. 只出现一次的数字 II
//给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
//你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
//示例 1：   输入：nums = [2, 2, 3, 2]      输出：3
//
// 如果考虑数组中每个数的二进制表示
// 那么将这些数的每一位二进制相加，模上 3，就能得到答案的二进制表示中对应位置的数
//
class Solution2 {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++)
        {
            int tmp = 0;
            for (auto& num : nums)
            {
                tmp += (num >> i) & 1;
            }
            ret += ((tmp % 3) << i);
        }
        return ret;
    }
};

// 第39 题 ##########################################################################################
//面试题 17.19.消失的两个数字
//给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
//以任意顺序返回这两个数字均可。
//示例 1:       输入: [1]     输出 : [2, 3]
// 
// 根据 268. 丢失的数字 这个题目的解法，能够得到到 a ^ b，而且 a 和 b 不同，所以a ^ b != 0
// 那么假设 keynum = a ^ b, 记 keynum 的二进制表示的最右边的 1 在第 x 位， 那么nums中的数总可以分成两个集合
//     s1. num 中第 x 位是 1
//     s2. num 中第 x 位是 0
//         s1中的数一一异或，得到的是 a, s2 中的数一一异或，得到的是 b
//
class Solution3 {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int XORtotal = 0;
        for (auto& num : nums)
        {
            XORtotal ^= num;
        }

        for (int i = 1; i <= nums.size() + 2; i++)
        {
            XORtotal ^= i;
        }

        int judgeDigit = XORtotal & (-XORtotal);
        int XORtot1 = 0;
        int XORtot2 = 0;
        for (int i = 1; i <= nums.size() + 2; i++)
        {
            if (judgeDigit & i)
            {
                XORtot1 ^= i;
            }
            else
            {
                XORtot2 ^= i;
            }
        }

        for (auto& num : nums)
        {
            if (judgeDigit & num)
            {
                XORtot1 ^= num;
            }
            else
            {
                XORtot2 ^= num;
            }
        }

        vector<int> ret = { XORtot1, XORtot2 };
        return ret;
    }
};

int main()
{
    Solution3 solu;
    vector<int> input = { 1 };
    vector<int> ret = solu.missingTwo(input);

    return 0;
}